The importance of error correction coding of data in digital computer systems has increased greatly as the density of the data recorded on mass storage media, more particularly magnetic tape, has increased. With higher recording densities, a tiny imperfection in the tape can corrupt a large amount of data. In order to avoid losing that data, error correction codes ("ECC's") are employed to, as the name implies, correct the erroneous data.
Before a string of data symbols is recorded on a tape, it is mathematically encoded to form redundancy symbols. The redundancy symbols are then appended to the data string to form code words--data symbols plus redundancy symbols. The code words are stored on the tape. When the stored data is to be accessed from the tape, the code words containing the data symbols are retrieved from the tape and mathematically decoded. During decoding any errors in the data are detected and, if possible, corrected through manipulation of the redundancy symbols [For a detailed description of decoding see Peterson and Weldon, Error-Correcting Codes, 2d Edition, MIT Press, 1972].
Stored digital data can contain multiple independent errors. One of the most effective types of error correction codes used for the correction of these multiple errors is a Reed-Solomon code [For a detailed description of Reed-Solomon codes, see Peterson and Weldon, Error-Correcting Codes]. To correct multiple errors in strings of data symbols, Reed-Solomon codes efficiently and effectively utilize the various mathematical properties of sets of symbols known as Galois Fields, represented by "GF(P.sup.q)", where "P" is a prime number and "q" can be thought of as the number of digits, base P, in each element or symbol in the field. "P" usually has the value 2 in digital computer applications and, therefore, "q" is the number of bits in each symbol.
Data is typically stored on a tape in a long sequence of symbols. Errors in data stored on a tape often occur in long bursts, that is, many erroneous symbols in a row. Techniques designed for detecting and/or correcting single or multiple independent errors, which do not ordinarily occur in bursts, are not well suited for the detection or correction of these long burst errors. Thus special error detection and/or correction techniques are typically employed to handle these long burst errors.
Techniques for the detection of long burst errors currently in use detect single or double bursts with each burst containing up to a predetermined maximum number of erroneous symbols. A code which detects bursts containing a larger number of erroneous symbols is considered more powerful than a code which detects bursts containing fewer erroneous symbols. For example, a well known Fire code detects double bursts of up to 22 bits each in 2 kilobytes of data and a well known, more powerful Burton code detects double bursts of up to 26 bits in 2 kilobytes of data. As the density of the data stored on tapes increases, the number of data symbols involved in the long burst errors increases, also. Such long burst errors may occur soon in data stored on disks due to increases in the density of the stored data. Thus a mechanism is desirable for detecting longer error bursts.
Once a long burst error is detected the erroneous symbols involved are corrected, if possible. The faster the errors can be corrected, the faster the data can be made available to a user. Thus the effective data transfer rate increases as the speed of error correction increases. Accordingly, a mechanism is desirable for quickly correcting the detected long burst errors.